/**
 * //给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：head = [1,2,3,4,5], n = 2
 * //输出：[1,2,3,5]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：head = [1], n = 1
 * //输出：[]
 * //
 * //
 * // 示例 3：
 * //
 * //
 * //输入：head = [1,2], n = 1
 * //输出：[1]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 链表中结点的数目为 sz
 * // 1 <= sz <= 30
 * // 0 <= Node.val <= 100
 * // 1 <= n <= sz
 * //
 * //
 * //
 * //
 * // 进阶：你能尝试使用一趟扫描实现吗？
 * //
 * // Related Topics 链表 双指针 👍 2257 👎 0
 */

package com.xixi.dataStructure.lineList;

public class ID00019RemoveNthNodeFromEndOfList {
    public static void main(String[] args) {
        Solution solution = new ID00019RemoveNthNodeFromEndOfList().new Solution();
    }


//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {

            ListNode resHead = new ListNode();

            resHead.next = head;

            int lineListLength = 0;

            ListNode pin = head;
            ListNode preLastN = resHead;
            while (pin != null) {
                lineListLength++;
                pin = pin.next;
                if (lineListLength > n) { //超过n开始之后，开始移动慢指针, 慢指针指向n的前置节点
                    preLastN = preLastN.next;
                }
            }

            preLastN.next = preLastN.next.next; //跨过当前节点


            return resHead.next;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}